package 力扣;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: a
 * Date: 2022-09-05
 * Time: 8:35
 */
public class find_duplicate_subtrees {
    private Map<String, Integer> key_id = new HashMap<>();
    private Map<String, Integer> key_count = new HashMap<>();
    private Set<String> set = new HashSet<>();
    private List<TreeNode> res = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        //getId(root);
        getKey(root);
        return res;
    }

    private String getKey(TreeNode node){
        if(node == null){
            return "#";
        }
        String key = String.valueOf(node.val) + "#" + String.valueOf(node.left) + "#" + String.valueOf(node.right);
        if(!set.contains(key)){
            set.add(key);
        }else{
            res.add(node);
        }
        return key;
    }

    //建立映射的关系(每一个序列化子树都有其对应的id, 存在哈希表中)
    private int getId(TreeNode node){
        if(node == null){
            return -1;
        }
        String key = String.valueOf(node.val) + "#" + String.valueOf(getId(node.left)) + "#" + String.valueOf(getId(node.right));
        if(key_id.get(key) == null){
            key_id.put(key, key_id.size());
            key_count.put(key, 1);
        }else{
            key_count.put(key, key_count.get(key) + 1);
            if(key_count.get(key) == 2){
                res.add(node);
            }
        }
        return key_id.get(key);
    }
}
